//#include <iostream>  
//#include <cstring>  
//#include <algorithm>  
//#include <string>  
//using namespace std;
//const int  N = 120;
//int dp[N][N];
//int main()
//{
//	string s;
//	while (cin >> s)
//	{
//		if (s == "end")
//			break;
//		memset(dp, 0, sizeof(dp));
//		for (int i = 1; i<s.size(); i++)
//		{
//			for (int j = 0, k = i; k<s.size(); j++, k++)
//			{
//				if (s[j] == '('&&s[k] == ')' || s[j] == '['&&s[k] == ']')
//					dp[j][k] = dp[j + 1][k - 1] + 2;
//				for (int f = j; f<k; f++)
//					dp[j][k] = max(dp[j][k], dp[j][f] + dp[f + 1][k]);
//			}
//		}
//		cout << dp[0][s.size() - 1] << endl;
//	}
//	return 0;
//}
#include <stdio.h>  
#include <string> 
#include <string.h>
#include <algorithm>
#include<iostream>
using namespace std; 
#define MAX 101  
int dp[MAX][MAX];
int main(void)
{
	int n, m, i, j, k;
	string str;
	scanf_s("%d", &n);
	while (n--)
	{
		cin >> str;
		int length = str.size();
		memset(dp, 0, sizeof(dp));
		for (i = 0; i < length; i++)
		{
			dp[i][i] = 1;
		}
		for (m = 2; m <= length; m++)
		{
			for (i = 0; i <= length - m; i++)
			{
				j = i + m-1;
				dp[i][j] = MAX;
				if (str[i]=='('&&str[j]==')'|| str[i] == '['&&str[j] == ']')
					dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
				for (k = i; k < j; k++)
				{
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
				}
			}
		}
		printf("%d\n", dp[0][length - 1]);
	}
	return 0;
}